package com.peng.tree.test_code.dp;

import com.peng.tree.Node;

/**
 * 是否是一颗搜索二叉树：
 * 1、左树是搜索二叉树
 * &&
 * 2、右树是搜索二叉树
 * &&
 * 3、当前节点>左树最大值  && 当前节点 < 右树最小值
 */
public class Test07_IsBinarySearchTree {

    public static boolean isBinarySearchTree(Node node) {
        if (node == null) {
            return false;
        }
        return process(node).isBST;
    }


    public static TreeInfo process(Node node) {
        if (node == null) {
            return null;
        }

        TreeInfo leftInfo = process(node.left);
        TreeInfo rightInfo = process(node.right);

        boolean isBST = true;
        int min = node.value;
        int max = node.value;
        if (leftInfo != null) {
            isBST = leftInfo.isBST && leftInfo.max < node.value;
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
        }
        if (rightInfo != null) {
            isBST = isBST && rightInfo.isBST && rightInfo.min > node.value;
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
        }

        return new TreeInfo(isBST, max, min);

    }

    public static void main(String[] args) {
        Node node = new Node(30);
        Node node2 = new Node(20);
        Node node3 = new Node(40);
        Node node4 = new Node(10);
        Node node5 = new Node(25);
        Node node6 = new Node(32);
        Node node7 = new Node(60);
        Node node8 = new Node(6);
        Node node9 = new Node(13);

        node.left = node2;
        node.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;

         /*
                   30
             20              40
           10    15         32     60
         6   13

         */
        System.out.println(isBinarySearchTree(node));
    }

    static class TreeInfo {
        boolean isBST;
        int max;
        int min;

        public TreeInfo(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }
}
